Among all of the different electrochemical couples upon which energy storage devices can be based, metal-air systems can exhibit the largest theoretical specific energies. For example, a lithium-air system can exhibit a theoretical specific energy of 11,972 Wh/kg. However, electrochemical performance of metal-air batteries can depend greatly on many factors including the properties of the carbon-based air electrode. While various nanostructured carbon materials have been explored in attempts to improve metal-air energy storage devices, the practical capacity, specific energy and rate performance of such devices has not been sufficient for most energy storage applications. Accordingly, an improved metal-air energy storage device is needed.